package Queue;

/**
 *  题目 ：设计前中后队列
 *  题目详述 ：
 *
 * 请你设计一个队列，支持在前，中，后三个位置的 push和 pop操作。
 * 请你完成FrontMiddleBack类：
 * FrontMiddleBack()初始化队列。
 * void pushFront(int val) 将val添加到队列的 最前面。
 * void pushMiddle(int val) 将val添加到队列的 正中间。
 * void pushBack(int val)将val添加到队里的 最后面。
 * int popFront()将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
 * int popMiddle() 将 正中间的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
 * int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
 *
 * 请注意当有两个中间位置的时候，选择靠前面的位置进行操作。比方说：
 *
 * 将 6添加到[1, 2, 3, 4, 5]的中间位置，结果数组为[1, 2, 6, 3, 4, 5]。
 * 从[1, 2, 3, 4, 5, 6]的中间位置弹出元素，返回3，数组变为[1, 2, 4, 5, 6]。
 *
 */
public class FrontMiddleBackQueue {
    /**
     *  核心思想 ：
     *  方法一 ：双向链表
     *  即，使用双向链表来模拟双端队列；
     */

    ListNode head; // 头指针指向链表头结点的前一个索引
    ListNode tail; // 尾指针指向链表尾结点的后一个索引
    Integer size; // 链表的大小
    public FrontMiddleBackQueue() {
        // 初始化头指针/尾指针
        head = new ListNode();
        tail = new ListNode();
        // 初始化链表大小
        size = 0;
        // head 和 tail 分别指向的是虚拟头结点，虚拟尾结点；
        head.next = tail;
        tail.pre = head;
    }

    public void pushFront(int val) {
        // 使用虚拟头结点，来向双向链表中插入新结点；
        insert(head , head.next , val);
        size++; // 链表长度 + 1
    }

    public void pushMiddle(int val) {
        int num = size / 2 ;
        ListNode mid = findMid(num);
        insert(mid,mid.next,val);
        size++;
    }

    public void pushBack(int val) {
        // 使用尾结点的下一个索引指针，来向双向链表中插入新结点；
        insert(tail.pre , tail , val);
        size++; // 链表长度 + 1
    }

    public int popFront() {
        // 若是链表为空的话，即直接返回不存在的值
        if(isEmpty()){
            return -1;
        }
        // 删除头结点所指向的下一个结点
        int deleteNode = delete(head.next);
        size--; // 链表长度 - 1
        return deleteNode;
    }

    public int popMiddle() {
        // 若是链表为空的话，即直接返回不存在的值
        if(isEmpty()){
            return -1;
        }
        int num = size / 2;
        ListNode mid = findMid(num);
        if(size % 2 == 1){
            // 由于此处还需要使用到size的值，不能够对其进行提前操作
            mid = mid.next;
        }
        size--; // 链表长度 - 1
        return delete(mid);
    }

    public int popBack() {
        // 若是链表为空的话，即直接返回不存在的值
        if(isEmpty()){
            return -1;
        }
        // 删除尾结点所指向的前一个结点
        int deleteNode = delete(tail.pre);
        size--; // 链表长度 - 1
        return deleteNode;
    }

    public Boolean isEmpty(){
        if(size == 0){
            return true;
        }
        return false;
    }

    public ListNode findMid(int num) {
        ListNode temp = head;
        for(int i = 0 ; i < num ; i++){
            temp = temp.next;
        }
        return temp;
    }
    public void insert(ListNode node1 , ListNode node2 , int val){
        ListNode listNode = new ListNode(val);
        // 插入新节点
        node1.next = listNode;
        listNode.pre = node1;
        listNode.next = node2;
        node2.pre = listNode;
    }

    public int delete(ListNode node){
        ListNode pre = node.pre; // 获取所要删除结点的上一个结点
        ListNode next = node.next; // 获取所要删除结点的下一个结点
        // 所要删除结点的上下结点相互指向；
        pre.next = next;
        next.pre = pre;
        return node.value;
    }
    class ListNode{
        ListNode pre;
        ListNode next;
        int value;
        public ListNode(){

        }
        public ListNode(int value){
            this.value = value;
        }
    }


    /**
     *  核心思想 ：
     *  直接使用双端队列
     */

}
